	\begin{usection}{861. Little Bishops}
		\url{http://uva.onlinejudge.org/external/8/861.html}\\
		
		Este problema se trata de encontrar la cantidad de formas de distribuír $k$ alfiles en un tablero de $n\times n$ sin que se ataquen entre sí.

		\begin{usubsection}{Idea}

			Este problema, dado que las dimensiónes de los parámetros
			eran realmente muy pequeñas, lo resolvimos directamente
			con un algoritmo de backtracking que prueba todas las
			combinaciones posibles.

			En primer lugar, dado que la posición de los alfiles que
			estan en los casilleros negros no influye de ninguna manera
			sobre la posición de los alfiles que estan en los casilleros
			blancos, separamos el problema de manera que para cada
			distribución posible de alfiles en los dos colores, la cantidad
			de formas de posicionarlos es el producto entre la cantidad
			de formas de posicionar cada uno de los dos conjuntos en los casilleros de su respectivo color.
			Luego sumamos estos resultados.

			Dado un color, podemos definir la posición de un alfil como
			la intersección entre 2 diagonales del tablero. Y dada esta
			definición, podemos además decir que 2 alfiles se cruzan sii
			comparten alguna diagonal.

			Luego la cantidad de formas de distribuir $k$ alfiles en
			un color, es la cantidad de subconjuntos distintos de $k$
			pares no ordenados de diagonales de tal manera que éstas
			sean distintas 2 a 2 en dicho subconjunto.

		\end{usubsection}
		
		\begin{usubsection}{Complejidad}

%			Ya que contamos una vez cada uno de los subconjuntos de
%			pares de diagonales mencionados en en párrafo anterior,
%			la complejidad es la cantidad de estos subconjuntos que
%			existen.

%			Como cada color tiene \Ode{n} diagonales, la cantidad de
%			pares de diagonales distintas es \Ode{n^2}. Por lo tanto la
%			cantidad de subconjuntos de $k$ elementos distintos en un
%			conjunto de $n^2$ elementos está dada por la combinatoria
%			$\binom{n^2}{k} = \frac{(n^2)!}{k!(n^2-k)!}$

%			Y esta cuenta la hacemos tantas veces como formas haya de
%			distribuir $k$ elementos iguales en 2 conjuntos. Como mucho
%			elegimos $k$, para el primer conjunto, luego $k-1$, y asi
%			sucesivamente llegamos a que son $k$ formas.

%			Por lo tanto la complejidad del algoritmo es
%			\Ode{k}\Ode{\frac{(n^2)!}{k!(n^2-k)!}} $=$
%			\Ode{\frac{(n^2)!}{k!(n^2-k)!}}.

			Si vemos el código, vemos que para calcular la cantidad de
			formas de colocar $k$ alfiles en un color, llamamos $k$
			veces a la recursión de la función, que itera cada vez sobre
			las posiciones de este color que hay en el tablero, las
			cuáles son del orden de \Ode{n^2}. Por lo cuál, la
			complejidad de la llamada original es de \Ode{kn^2}.

			Luego, esta llamada sucede tantas veces como formas haya de
			distribuir los alfiles en 2 conjuntos. si ponemos $k$
			alfiles en un conjunto, tenemos que poner $n-k$ en el otro.
			Como no tiene sentdo poner más de $n$ alfiles en un color,
			nos queda llamar a la función para $k = 0 \rightarrow n$ para un color
			y $k = n \rightarrow 0$ para el otro. lo cuál nos da una complejidad de
			\Ode{2\sum_{i=0}^{n}{i\times n^2}} = \Ode{2n^2\sum_{i=0}^{n}{i}} = \Ode{n^4}.
			

		\end{usubsection}

	\end{usection}
